In recent years, significant advances in both networking technology and technologies involving the digitization and compression of video have taken place. For example, it is now possible to transmit several gigabits of data per second over fiber optic networks and with compression standards like MPEG-1, the bandwidth required for transmitting video is relatively low. These advances have resulted in a host of new applications involving the transmission of video data over communications networks, such as video-on-demand, on-line tutorials, interactive television, etc.
Video servers are one of the key components necessary to provide the above applications. Depending on the application, the video servers may be required to store hundreds of video programs and concurrently transmit data for a few hundred to a few thousand videos to clients. As would be understood, the transmission rate is typically a fixed rate contingent upon the compression technique employed by the video server. For example, the transmission rate for MPEG-1 is approximately 1.5 Mbps.
Videos, for example movies and other on-demand programming, are transmitted from the random access memory (RAM) of the video server to the clients. However, due to the voluminous nature of video data (e.g., a hundred minute long MPEG-1 video requires approximately 1.125 GB of storage space) and the relatively high cost of RAM, storing videos in RAM is prohibitively expensive. A cost effective alternative manner for storing videos on a video server involves utilizing magnetic or optical disks instead of RAM. Video stored on disks, however, needs to be retrieved into RAM before it can be transmitted to the clients by the video server. Modem magnetic and optical disks, however, have limited storage capacity, e.g., 1 GB to 9 GB, and relatively low transfer rates for retrieving data from these disks to RAM, e.g., 30 Mbps to 60 Mbps. This limited storage capacity affects the number of videos that can be stored on the video server and, along with the low transfer rates, affects the number of videos that can be concurrently retrieved.
A naive storage scheme in which an entire video is stored on an arbitrarily chosen disk could result in disks with popular video programming being over-burdened with more requests than can be supported, while other disks with less popular video programs remain idle. Such a scheme results in an ineffective utilization of disk bandwidth. As would be understood, the term "disk bandwidth" refers to the amount of data which can be retrieved from a disk over a period of time. When data is not being retrieved from a disk, such as when the disk is idle or when a disk head is being positioned, disk bandwidth is not being utilized, and is thus considered wasted. Ineffective utilization of disk bandwidth adversely affects the number of concurrent streams a video server can support.
To utilize disk bandwidth more effectively, various schemes have been devised where the workload is distributed uniformly across multiple disks, i.e., videos are laid out on more than one disk. One popular method for storing videos across a plurality of disks is disk striping, a well known technique in which consecutive logical data units (referred to herein as "stripe units") are distributed across a plurality of individually accessible disks in a round-robin fashion. Disk striping, in addition to distributing the workload uniformly across disks, also enables multiple concurrent streams of a video to be supported without having to replicate the video.
Outstanding requests for videos are generally serviced by the video server in the order in which they were received, i.e., first-in-first-out (FIFO). Where the number of concurrent requests is less than or not much greater than the number of concurrent streams that can be supported by the server, good overall response times to all outstanding requests are possible. In video-on-demand (VOD) environments, however, where the number concurrent requests, typically, far exceeds the number of concurrent streams that can be supported by the server, good overall response times are not possible for all outstanding requests using FIFO.
To provide better overall response times, a paradigm known as enhanced pay-per-view (EPPV) was adopted by VOD environments, such as cable and broadcasting companies. Utilizing the enhanced pay per view paradigm, video servers retrieve and transmit video streams to clients at fixed intervals or periods. Under this paradigm, the average response time for a request is half of the fixed interval and the worst case response time for a request would be the fixed interval. Furthermore, by retrieving popular videos more frequently, and less popular video less frequently, better overall average response times could be achieved. Finally, by informing the clients about the periods and the exact times at which videos are retrieved, zero response times can be provided.
Although a set of videos are scheduleable on a video server employing the EPPV paradigm, determining an exact schedule for which new streams of videos are to begin can be difficult, particularly when the periods and computation times, i.e., time required to transmit a video or segment, are arbitrary. The goal is to schedule the set of videos such that the number of streams scheduled to be transmitted concurrently does not exceed the maximum number of concurrent streams supportable by the video server. The complexity of scheduling videos in an EPPV paradigm is NP-hard--wherein the complexity of scheduling periodic videos increases exponentially as the number of videos being scheduled and the number of processors by which the videos are transmitted increases. Accordingly, there is a need for a method and apparatus which can effectively schedule videos periodically on a video server employing the EPPV paradigm.